{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## 1.3 \u4fdd\u7559\u6700\u540e N \u4e2a\u5143\u7d20\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u95ee\u9898\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5728\u8fed\u4ee3\u64cd\u4f5c\u6216\u8005\u5176\u4ed6\u64cd\u4f5c\u7684\u65f6\u5019\uff0c\u600e\u6837\u53ea\u4fdd\u7559\u6700\u540e\u6709\u9650\u51e0\u4e2a\u5143\u7d20\u7684\u5386\u53f2\u8bb0\u5f55\uff1f"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u89e3\u51b3\u65b9\u6848\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4fdd\u7559\u6709\u9650\u5386\u53f2\u8bb0\u5f55\u6b63\u662f collections.deque \u5927\u663e\u8eab\u624b\u7684\u65f6\u5019\u3002\u6bd4\u5982\uff0c\u4e0b\u9762\u7684\u4ee3\u7801\u5728\u591a\u884c\u4e0a\u9762\u505a\u7b80\u5355\u7684\u6587\u672c\u5339\u914d\uff0c\n\u5e76\u8fd4\u56de\u5339\u914d\u6240\u5728\u884c\u7684\u6700\u540eN\u884c\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "from collections import deque\n\n\ndef search(lines, pattern, history=5):\n    previous_lines = deque(maxlen=history)\n    for line in lines:\n        if pattern in line:\n            yield line, previous_lines\n        previous_lines.append(line)\n\n# Example use on a file\nif __name__ == '__main__':\n    with open(r'../../cookbook/somefile.txt') as f:\n        for line, prevlines in search(f, 'python', 5):\n            for pline in prevlines:\n                print(pline, end='')\n            print(line, end='')\n            print('-' * 20)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u8ba8\u8bba\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u6211\u4eec\u5728\u5199\u67e5\u8be2\u5143\u7d20\u7684\u4ee3\u7801\u65f6\uff0c\u901a\u5e38\u4f1a\u4f7f\u7528\u5305\u542b yield \u8868\u8fbe\u5f0f\u7684\u751f\u6210\u5668\u51fd\u6570\uff0c\u4e5f\u5c31\u662f\u6211\u4eec\u4e0a\u9762\u793a\u4f8b\u4ee3\u7801\u4e2d\u7684\u90a3\u6837\u3002\n\u8fd9\u6837\u53ef\u4ee5\u5c06\u641c\u7d22\u8fc7\u7a0b\u4ee3\u7801\u548c\u4f7f\u7528\u641c\u7d22\u7ed3\u679c\u4ee3\u7801\u89e3\u8026\u3002\u5982\u679c\u4f60\u8fd8\u4e0d\u6e05\u695a\u4ec0\u4e48\u662f\u751f\u6210\u5668\uff0c\u8bf7\u53c2\u770b 4.3 \u8282\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4f7f\u7528 deque(maxlen=N) \u6784\u9020\u51fd\u6570\u4f1a\u65b0\u5efa\u4e00\u4e2a\u56fa\u5b9a\u5927\u5c0f\u7684\u961f\u5217\u3002\u5f53\u65b0\u7684\u5143\u7d20\u52a0\u5165\u5e76\u4e14\u8fd9\u4e2a\u961f\u5217\u5df2\u6ee1\u7684\u65f6\u5019\uff0c\n\u6700\u8001\u7684\u5143\u7d20\u4f1a\u81ea\u52a8\u88ab\u79fb\u9664\u6389\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4ee3\u7801\u793a\u4f8b\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "q = deque(maxlen=3)\nq.append(1)\nq.append(2)\nq.append(3)\nq"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "q.append(4)\nq"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "q.append(5)\nq"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5c3d\u7ba1\u4f60\u4e5f\u53ef\u4ee5\u624b\u52a8\u5728\u4e00\u4e2a\u5217\u8868\u4e0a\u5b9e\u73b0\u8fd9\u4e00\u7684\u64cd\u4f5c\uff08\u6bd4\u5982\u589e\u52a0\u3001\u5220\u9664\u7b49\u7b49\uff09\u3002\u4f46\u662f\u8fd9\u91cc\u7684\u961f\u5217\u65b9\u6848\u4f1a\u66f4\u52a0\u4f18\u96c5\u5e76\u4e14\u8fd0\u884c\u5f97\u66f4\u5feb\u4e9b\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u66f4\u4e00\u822c\u7684\uff0c deque \u7c7b\u53ef\u4ee5\u88ab\u7528\u5728\u4efb\u4f55\u4f60\u53ea\u9700\u8981\u4e00\u4e2a\u7b80\u5355\u961f\u5217\u6570\u636e\u7ed3\u6784\u7684\u573a\u5408\u3002\n\u5982\u679c\u4f60\u4e0d\u8bbe\u7f6e\u6700\u5927\u961f\u5217\u5927\u5c0f\uff0c\u90a3\u4e48\u5c31\u4f1a\u5f97\u5230\u4e00\u4e2a\u65e0\u9650\u5927\u5c0f\u961f\u5217\uff0c\u4f60\u53ef\u4ee5\u5728\u961f\u5217\u7684\u4e24\u7aef\u6267\u884c\u6dfb\u52a0\u548c\u5f39\u51fa\u5143\u7d20\u7684\u64cd\u4f5c\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4ee3\u7801\u793a\u4f8b\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "q = deque()\nq.append(1)\nq.append(2)\nq.append(3)\nq"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "q.appendleft(4)\nq"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "q.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "q"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "q.popleft()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5728\u961f\u5217\u4e24\u7aef\u63d2\u5165\u6216\u5220\u9664\u5143\u7d20\u65f6\u95f4\u590d\u6742\u5ea6\u90fd\u662f O(1) \uff0c\u533a\u522b\u4e8e\u5217\u8868\uff0c\u5728\u5217\u8868\u7684\u5f00\u5934\u63d2\u5165\u6216\u5220\u9664\u5143\u7d20\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a O(N) \u3002"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.1"
    },
    "toc": {
      "base_numbering": 1,
      "nav_menu": {},
      "number_sections": true,
      "sideBar": true,
      "skip_h1_title": true,
      "title_cell": "Table of Contents",
      "title_sidebar": "Contents",
      "toc_cell": false,
      "toc_position": {},
      "toc_section_display": true,
      "toc_window_display": true
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}